def bellman_ford(s):
    d = [maxint] * len(V)
    d[s] = 0
    for i in xrange(len(V) - 1): 
        for e in xrange(m):
            u = x[e]
            v = y[e]
            if d[u] < maxint:
                d[v] = min(d[v], d[u] + w[e])
    return d

if __name__=='__main__':
    from sys import maxint
    from pprint import pprint
    Adj = [[(1,10),(2,5)],[(2,2),(3,1)],[(1,3),(3,9),(4,2)],[(4,4)],[(3,6),(0,7)]] #CLRS pp.595
    print 'Adj: Adj[u] stores (v,w[u,v])'
    pprint(Adj)
    
    V = xrange(len(Adj))
    m = 0 # # of edges
    x = {}
    y = {}
    w = {}
    for u in V:
        for v, ww in Adj[u]:
            x[m] = u
            y[m] = v
            w[m] = ww
            m += 1

    d = bellman_ford(0)
    print 'd :', d